﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace T16Generid
{
    class Program
    {
        static void Main(string[] args)
        {
            //泛型具体：类型安全
            BTreeNode<string> root = new BTreeNode<string>("北京");
            root.Letf = new BTreeNode<string>("石家庄");
            root.Right = new BTreeNode<string>("济南");
            root.Letf.Letf  = new BTreeNode<string>("太原");
            root.Letf .Right  = new BTreeNode<string>("郑州");
            root.Right.Letf = new BTreeNode<string>("徐州");
            root.Right.Right  = new BTreeNode<string>("青岛");
            root.Letf.Right.Letf  = new BTreeNode<string>("西安");
            root.Letf.Right.Right  = new BTreeNode<string>("武汉");
            root.Right.Letf.Letf  = new BTreeNode<string>("南京");
            root.Right.Letf.Right = new BTreeNode<string>("连云港");
            Console.WriteLine("前序遍历：");
            root.PreorderTraverse();
            Console.WriteLine("\n中序遍历：");
            root.InorderTraverse();
            Console.WriteLine("\n后序遍历：");
            root.PostorderTraverse();

            BTreeNode<int> root2 = new BTreeNode<int>(0);
            root2.Letf  = new BTreeNode<int>(-1);
            root2.Right  = new BTreeNode<int>(1);
            root2.Right.Right  = new BTreeNode<int>(2);
            Console.WriteLine("\n中序遍历：");
            root2.InorderTraverse();
            BTreeNode<int> node = root2 << 2;
            Console.WriteLine(node);
            Console.WriteLine("\n中序遍历：");
            node.InorderTraverse();

            Console.ReadKey();
        }

        /// <summary>
        /// 二叉树泛型实现
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public class BTreeNode<T>
        {
            private T data;
            public T Data
            {
                get { return data; }
                set
                {
                    if (!data.Equals(value))//说明T必须实现了Equals
                        data = value;
                }
            }
            //递归定义
            public BTreeNode<T> Letf { get; set; }
            public BTreeNode<T> Right { get; set; }

            public BTreeNode (T data)
            {
                this.data = data;
            }

            /// <summary>
            /// 先序遍历
            /// </summary>
            public void PreorderTraverse()
            {
                Console.WriteLine(this .data .ToString ()+' ');
                if (this.Letf != null)
                    this.Letf.PreorderTraverse();
                if (this.Right  != null)
                    this.Right .PreorderTraverse();
            }

            /// <summary>
            /// 中序遍历
            /// </summary>
            public void  InorderTraverse()
            {
                if (this.Letf != null)
                    this.Letf.InorderTraverse();
                Console.WriteLine(this.data.ToString() + ' ');
                if (this.Right  != null)
                    this.Right .InorderTraverse();               
            }

            /// <summary>
            /// 后序遍历
            /// </summary>
            public void PostorderTraverse()
            {
                if (this.Letf != null)
                    this.Letf.InorderTraverse();                
                if (this.Right != null)
                    this.Right.InorderTraverse();
                Console.WriteLine(this.data.ToString() + ' ');
            }

            /// <summary>
            /// 获取指定第N层的左子树
            /// </summary>
            /// <param name="node"></param>
            /// <param name="n"></param>
            /// <returns></returns>
            public static BTreeNode <T> operator <<(BTreeNode <T> node,int n)
            {
                for (int i = 0; i < n&&node.Letf !=null ; i++)
                {
                    node = node.Letf;
                }
                return node;
            }


            /// <summary>
            /// 获取指定第N层的右子树
            /// </summary>
            /// <param name="node"></param>
            /// <param name="n"></param>
            /// <returns></returns>
            public static BTreeNode<T> operator >>(BTreeNode<T> node, int n)
            {
                for (int i = 0; i < n && node.Right  != null; i++)
                {
                    node = node.Right ;
                }
                return node;
            }

            public override string ToString()
            {
                return base.ToString();
            }
            
        }
        
    }
}
